import cv2
from cgi import test
from cv2 import mean
from importlib_metadata import distribution, re
from matplotlib.pyplot import step
import numpy as np
import math
import time
import sys
import os
import argparse
from colorama import Fore, Back, Style
from colorama import init

###############################################################################
# 2D wave function collapse
###############################################################################

Width = 8
Height = 8
entropy = []
candidates = [1,2,3,4,5]
candidates_X_symmetry = {1,2,3,4,5}
candidates_L_symmetry = {}
candidates_weight = [1,1,1,1,1]
weight_stack = []

oriented_candidates = []
oriented_candidates_weight = []
oriented_weight_stack = []

# the wave
# wave is a 2D array of size (W x H, number_of_candidates)
wave = []
wave_oriented = []

# concise rules
# (i,i_rot,j,j_rot)
concise_rules = {
    (1,0,1,0),
    (1,0,2,0),
    (2,0,2,0),
    (2,0,3,0),
    (3,0,3,0),
    (3,0,4,0),
    (4,0,4,0),
    (4,0,5,0),
    (5,0,5,0)
}

# all the compatible situations
# H for horizontal
# V for vertical
# Rotation: 0->0 , 1->90, 2->180, 3->270
rules = {
    (1,0,2,0),
    (2,0,3,0),
    (3,0,4,0),
    (4,0,5,0),
    (5,0,4,0),
    (4,0,3,0),
    (3,0,2,0),
    (2,0,1,0),
    (1,0,2,0),
    (2,0,3,0),
    (3,0,4,0),
    (4,0,5,0),
    (5,0,4,0),
    (4,0,3,0),
    (3,0,2,0),
    (2,0,1,0),
    (1,0,1,0),
    (1,0,1,0),
    (2,0,2,0),
    (2,0,2,0),
    (3,0,3,0),
    (3,0,3,0),
    (4,0,4,0),
    (4,0,4,0),
    (5,0,5,0),
    (5,0,5,0)
}

rules2 = {
    (1,0,2,0),
    (2,0,3,0),
    (3,0,4,0),
    (4,0,5,0),
    (1,0,1,0),
    (2,0,2,0),
    (3,0,3,0),
    (4,0,4,0),
    (5,0,5,0)
}

def rot_clockwise(tp = (0,0)):

    if tp[0] in candidates_X_symmetry:
        return tp
    else:
        if tp[1] <=2:
            tp1 = (tp[0],tp[1]+1)
            return tp1
        elif tp[1] == 3:
            tp1 = (tp[0],0)
            return tp1
        else:
            return tp

# symmetry generator
def symmetry_generator(rules2):

    print(rules2)

    rules_ = set()

    # for each rule in rules2, rotate clockwise 4 times
    for r in rules2:

        cand1 = (r[0],r[1])
        cand2 = (r[2],r[3])

        # rot 0
        rule_0 = r

        # rot 90
        rot_0_left = rot_clockwise(cand1)
        rot_0_right = rot_clockwise(cand2)
        rule_90 = (rot_0_left[0],rot_0_left[1],rot_0_right[0],rot_0_right[1])

        # rot 180
        rot_90_right = rot_clockwise(rot_clockwise(cand1))
        rot_90_left = rot_clockwise(rot_clockwise(cand2))
        rule_180 = (rot_90_left[0],rot_90_left[1],rot_90_right[0],rot_90_right[1])

        # rot 270
        rot_270_right = rot_clockwise(rot_clockwise(rot_clockwise(cand1)))
        rot_270_left = rot_clockwise(rot_clockwise(rot_clockwise(cand2)))
        rule_270 = (rot_270_left[0],rot_270_left[1],rot_270_right[0],rot_270_right[1])

        # add to rules
        rules_.add(rule_0)
        rules_.add(rule_90)
        rules_.add(rule_180)
        rules_.add(rule_270)

    print(rules_)
    return rules_

# collapse state detection
def collapse_detection(wave_index):
    if len(wave[wave_index]) != 1:
        return False
    else:
        return True

def collapse_detection2(wave_index):
    if len(wave_oriented[wave_index]) != 1:
        return False
    else:
        return True

def distributional_trigger(wavelet_index):

    collapse_element_index = 0

    # construct a new weight array for the wavelet
    weight_array = []
    for i in range(len(wave[wavelet_index])):
        weight_array.append(get_weight_of_candidate(wavelet_index,wave[wavelet_index][i]))

    # generate a random number in [0, sum(weight_array)]
    random_number = np.random.rand() * sum(weight_array)

    # find the collapse element
    for i in range(len(weight_array)):
        random_number -= weight_array[i]
        if random_number <= 0:
            collapse_element_index = i
            break

    return collapse_element_index

def distributional_trigger2(wavelet_index):

    collapse_element_index = 0

    # construct a new weight array for the wavelet
    weight_array = []
    for i in range(len(wave_oriented[wavelet_index])):
        weight_array.append(get_weight_of_candidate2(wavelet_index,wave_oriented[wavelet_index][i]))

    # generate a random number in [0, sum(weight_array)]
    random_number = np.random.rand() * sum(weight_array)

    # find the collapse element
    for i in range(len(weight_array)):
        random_number -= weight_array[i]
        if random_number <= 0:
            collapse_element_index = i
            break

    return collapse_element_index

# get weight through candidate
def get_weight_of_candidate(index, candidate):
    for i in range(len(candidates)):
        if candidates[i] == candidate:
            return weight_stack[index][i]

def get_weight_of_candidate2(index, candidate):
    for i in range(len(oriented_candidates)):
        if oriented_candidates[i] == candidate:
            return oriented_weight_stack[index][i]

def set_weight_of_candidate(index, candidate, weight):
    for i in range(len(candidates)):
        if candidates[i] == candidate:
            weight_stack[index][i] = weight

# calculate the Shannon entropy of a wavelet
def shannon_entropy_of_wavelet(index,wavelet):

    entropy = 0
    sum_weight = 0
    for i in wavelet:
        sum_weight += get_weight_of_candidate(index,i)

    for i in wavelet:
        probability = get_weight_of_candidate(index,i) / sum_weight
        probability = max(probability, 1e-10)
        entropy += -probability * math.log(probability)

    # add a small purturbation
    entropy += np.random.rand() * 1e-3

    return entropy

# calculate the Shannon entropy of a wavelet
def shannon_entropy_of_wavelet2(index,wavelet):

    entropy = 0
    sum_weight = 0
    for i in wavelet:
        sum_weight += get_weight_of_candidate2(index,i)

    for i in wavelet:
        probability = get_weight_of_candidate2(index,i) / sum_weight
        probability = max(probability, 1e-10)
        entropy += -probability * math.log(probability)

    # add a small purturbation
    entropy += np.random.rand() * 1e-3

    return entropy

# update entropy
def update_wave_entropy():
    for i in range(len(wave)):
        entropy[i] = shannon_entropy_of_wavelet(i,wave[i])

def update_wave_entropy2():
    for i in range(len(wave_oriented)):
        entropy[i] = shannon_entropy_of_wavelet2(i,wave_oriented[i])

# find an element to collapse
def find_minimum_entropy_position():
    # find minimum entropy index of entropy
    min_entropy_index = 0
    min_entropy = 1e10
    for i in range(len(entropy)):
        if entropy[i] < min_entropy and collapse_detection(i) == False:
            min_entropy = entropy[i]
            min_entropy_index = i

    return min_entropy_index

def find_minimum_entropy_position2():
    # find minimum entropy index of entropy
    min_entropy_index = 0
    min_entropy = 1e10
    for i in range(len(entropy)):
        if entropy[i] < min_entropy and collapse_detection2(i) == False:
            min_entropy = entropy[i]
            min_entropy_index = i

    return min_entropy_index

# propagate the wave function
# active-propagation
def propagate():
    
    # neighbors :
    #         (i,j-1)
    # (i-1,j) (i,j  ) (i+1,j)
    #         (i,j+1)

    for k in range(1):
        for j in range(Height):
            for i in range(Width):

                # if len(wave[j*Width+i]) == len(candidates):
                #     continue

                # if collapse_detection(j*Width+i) == True:
                #     continue

                i_0 = i-1
                j_0 = j-1
                i_1 = i+1
                j_1 = j+1

                wavelet_temp1 = set()
                wavelet_temp2 = set()
                wavelet_temp3 = set()
                wavelet_temp4 = set()

                # construct local context and compare it with rules
                # (i-1,j)
                if i_0 >= 0:
                    for element_i in wave[j*Width+i]:
                        for element_j in wave[j*Width+i_0]:
                            if len(wave[j*Width+i_0]) == 1:
                                break
                            if (element_j,0,element_i,0) in rules:
                                wavelet_temp1.add(element_j)
                # (i+1,j)
                if i_1 < Width:
                    for element_i in wave[j*Width+i]:
                        for element_j in wave[j*Width+i_1]:
                            if len(wave[j*Width+i_1]) == 1:
                                break
                            if (element_i,0,element_j,0) in rules:
                                wavelet_temp2.add(element_j)
                # (i,j-1)
                if j_0 >= 0:
                    for element_i in wave[j*Width+i]:
                        for element_j in wave[j_0*Width+i]:
                            if len(wave[j_0*Width+i]) == 1:
                                break
                            if (element_j,0,element_i,0) in rules:
                                wavelet_temp3.add(element_j)
                # (i,j+1)
                if j_1 < Height:
                    for element_i in wave[j*Width+i]:
                        for element_j in wave[j_1*Width+i]:
                            if len(wave[j_1*Width+i]) == 1:
                                break
                            if (element_i,0,element_j,0) in rules:
                                wavelet_temp4.add(element_j)
                
                # update neighbors
                if len(wavelet_temp1) != 0:
                    wave[j*Width+i_0].clear()
                    for element in wavelet_temp1:
                        wave[j*Width+i_0].append(element)
                if len(wavelet_temp2) != 0:
                    wave[j*Width+i_1].clear()
                    for element in wavelet_temp2:
                        wave[j*Width+i_1].append(element)
                if len(wavelet_temp3) != 0:
                    wave[j_0*Width+i].clear()
                    for element in wavelet_temp3:
                        wave[j_0*Width+i].append(element)
                if len(wavelet_temp4) != 0:
                    wave[j_1*Width+i].clear()
                    for element in wavelet_temp4:
                        wave[j_1*Width+i].append(element)

    update_wave_entropy()


def propagate2():
    
    # neighbors :
    #         (i,j-1)
    # (i-1,j) (i,j  ) (i+1,j)
    #         (i,j+1)

    for k in range(1):
        for j in range(Height):
            for i in range(Width):

                # if len(wave[j*Width+i]) == len(candidates):
                #     continue

                # if collapse_detection(j*Width+i) == True:
                #     continue

                i_0 = i-1
                j_0 = j-1
                i_1 = i+1
                j_1 = j+1

                wavelet_temp1 = set()
                wavelet_temp2 = set()
                wavelet_temp3 = set()
                wavelet_temp4 = set()

                # construct local context and compare it with rules
                # (i-1,j)
                if i_0 >= 0:
                    for element_i in wave_oriented[j*Width+i]:
                        for element_j in wave_oriented[j*Width+i_0]:
                            if len(wave_oriented[j*Width+i_0]) == 1:
                                break
                            if (element_j[0],element_j[1],element_i[0],element_i[1]) in rules2:
                                wavelet_temp1.add(element_j)
                # (i+1,j)
                if i_1 < Width:
                    for element_i in wave_oriented[j*Width+i]:
                        for element_j in wave_oriented[j*Width+i_1]:
                            if len(wave_oriented[j*Width+i_1]) == 1:
                                break
                            if (element_i[0],element_i[1],element_j[0],element_j[1]) in rules2:
                                wavelet_temp2.add(element_j)
                # (i,j-1)
                if j_0 >= 0:
                    for element_i in wave_oriented[j*Width+i]:
                        for element_j in wave_oriented[j_0*Width+i]:
                            if len(wave_oriented[j_0*Width+i]) == 1:
                                break
                            if (element_j[0],element_j[1],element_i[0],element_i[1]) in rules2:
                                wavelet_temp3.add(element_j)
                # (i,j+1)
                if j_1 < Height:
                    for element_i in wave_oriented[j*Width+i]:
                        for element_j in wave_oriented[j_1*Width+i]:
                            if len(wave_oriented[j_1*Width+i]) == 1:
                                break
                            if (element_i[0],element_i[1],element_j[0],element_j[1]) in rules2:
                                wavelet_temp4.add(element_j)
                
                # update neighbors
                if len(wavelet_temp1) != 0:
                    wave_oriented[j*Width+i_0].clear()
                    for element in wavelet_temp1:
                        wave_oriented[j*Width+i_0].append(element)
                if len(wavelet_temp2) != 0:
                    wave_oriented[j*Width+i_1].clear()
                    for element in wavelet_temp2:
                        wave_oriented[j*Width+i_1].append(element)
                if len(wavelet_temp3) != 0:
                    wave_oriented[j_0*Width+i].clear()
                    for element in wavelet_temp3:
                        wave_oriented[j_0*Width+i].append(element)
                if len(wavelet_temp4) != 0:
                    wave_oriented[j_1*Width+i].clear()
                    for element in wavelet_temp4:
                        wave_oriented[j_1*Width+i].append(element)

    update_wave_entropy2()


# collapse the wavelet
def collapse_at_position(wavelet_index):
    
    collapse_element_index = distributional_trigger(wavelet_index)
    wavelet = []
    wavelet.append(wave[wavelet_index][collapse_element_index])
    wave[wavelet_index].clear()
    wave[wavelet_index] = wavelet.copy()

def collapse_at_position2(wavelet_index):
    
    collapse_element_index = distributional_trigger2(wavelet_index)
    wavelet = []
    wavelet.append(wave_oriented[wavelet_index][collapse_element_index])
    wave_oriented[wavelet_index].clear()
    wave_oriented[wavelet_index] = wavelet.copy()

def clear_screen():
    print('\033c',end='')

# check if the wave is collapsed
def is_collapsed(wave):
    for i in range(len(wave)):
        if collapse_detection(i) == False:
            return False
    return True

def is_collapsed2(wave_oriented):
    for i in range(len(wave_oriented)):
        if collapse_detection2(i) == False:
            return False
    return True

# contradiction check
def contradiction_check(wave):
    for j in range(Height):
        for i in range(Width):

            if collapse_detection(j*Width+i) == False:
                continue

            i_0 = i-1
            j_0 = j-1
            i_1 = i+1
            j_1 = j+1

            # construct local context and compare it with rules
            # (i-1,j)
            if i_0 >= 0:
                for element_i in wave[j*Width+i]:
                    for element_j in wave[j*Width+i_0]:
                        if not (element_j,0,element_i,0) in rules:
                            return False
            # (i+1,j)
            if i_1 < Width:
                for element_i in wave[j*Width+i]:
                    for element_j in wave[j*Width+i_1]:
                        if not (element_i,0,element_j,0) in rules:
                            return False
            # (i,j-1)
            if j_0 >= 0:
                for element_i in wave[j*Width+i]:
                    for element_j in wave[j_0*Width+i]:
                        if not (element_j,0,element_i,0) in rules:
                            return False
            # (i,j+1)
            if j_1 < Height:
                for element_i in wave[j*Width+i]:
                    for element_j in wave[j_1*Width+i]:
                        if not (element_i,0,element_j,0) in rules:
                            return False
    return True

def contradiction_check2(wave):
    for j in range(Height):
        for i in range(Width):

            if collapse_detection2(j*Width+i) == False:
                continue

            i_0 = i-1
            j_0 = j-1
            i_1 = i+1
            j_1 = j+1

            # construct local context and compare it with rules
            # (i-1,j)
            if i_0 >= 0:
                for element_i in wave_oriented[j*Width+i]:
                    for element_j in wave_oriented[j*Width+i_0]:
                        if not (element_j[0],element_j[1],element_i[0],element_i[1]) in rules2:
                            return False
            # (i+1,j)
            if i_1 < Width:
                for element_i in wave_oriented[j*Width+i]:
                    for element_j in wave_oriented[j*Width+i_1]:
                        if not (element_i[0],element_i[1],element_j[0],element_j[1]) in rules2:
                            return False
            # (i,j-1)
            if j_0 >= 0:
                for element_i in wave_oriented[j*Width+i]:
                    for element_j in wave_oriented[j_0*Width+i]:
                        if not (element_j[0],element_j[1],element_i[0],element_i[1]) in rules2:
                            return False
            # (i,j+1)
            if j_1 < Height:
                for element_i in wave_oriented[j*Width+i]:
                    for element_j in wave_oriented[j_1*Width+i]:
                        if not (element_i[0],element_i[1],element_j[0],element_j[1]) in rules2:
                            return False
    return True


# render the wave
def render(pass_ = False):

    for j in range(Height):
        for i in range(Width):
            sum_ = sum(wave[j*Width+i])
            mean = sum_ / len(wave[j*Width+i])
            mean_str = str(round(mean,2))
            entropy_str = str(round(entropy[j*Width+i],2))
            if pass_ == False:
                if len(wave[j*Width+i]) == len(candidates):
                    print(Style.RESET_ALL + mean_str + "," + Fore.LIGHTBLUE_EX, end=' ')
                elif len(wave[j*Width+i]) == 1:
                    print(Style.RESET_ALL + Fore.RED + mean_str + ",", end=' ')
                else:
                    print(Style.RESET_ALL + Fore.GREEN + "[" + mean_str + "]"+ ",", end=' ')
            else:
                print(Style.RESET_ALL + Fore.GREEN + "[" + mean_str + "]"+ ",", end=' ')
        print()

    if pass_:
        tile1 = np.zeros((20,20,3), np.uint8)
        tile2 = np.zeros((20,20,3), np.uint8)
        tile2[:,:] = (50,50,50)
        tile3 = np.zeros((20,20,3), np.uint8)
        tile3[:,:] = (100,100,100)
        tile4 = np.zeros((20,20,3), np.uint8)
        tile4[:,:] = (150,150,150)
        tile5 = np.zeros((20,20,3), np.uint8)
        tile5[:,:] = (200,200,200)
        tiles = [] 
        tiles.append(tile1)
        tiles.append(tile2)
        tiles.append(tile3)
        tiles.append(tile4)
        tiles.append(tile5)
        # conbine Height x Width tiles into a single image
        canvas = np.zeros((Height*20,Width*20,3), np.uint8)
        for j in range(Height):
            for i in range(Width):
                if collapse_detection(j*Width+i) == True:
                    canvas[j*20:(j+1)*20,i*20:(i+1)*20] = tiles[wave[j*Width+i][0]-1].copy()

        # display the image
        cv2.imshow('image',canvas)
        cv2.waitKey(1)

def render_wave(wave_,window_name_ = "wave",to_file_ = False,img_id = 0):

    tile1 = np.zeros((20,20,3), np.uint8)
    tile2 = np.zeros((20,20,3), np.uint8)
    tile2[:,:] = (50,50,50)
    tile3 = np.zeros((20,20,3), np.uint8)
    tile3[:,:] = (100,100,100)
    tile4 = np.zeros((20,20,3), np.uint8)
    tile4[:,:] = (150,150,150)
    tile5 = np.zeros((20,20,3), np.uint8)
    tile5[:,:] = (200,200,200)
    tiles = [] 
    tiles.append(tile1)
    tiles.append(tile2)
    tiles.append(tile3)
    tiles.append(tile4)
    tiles.append(tile5)
    # conbine Height x Width tiles into a single image
    canvas = np.zeros((Height*20,Width*20,3), np.uint8)
    for j in range(Height):
        for i in range(Width):
            if collapse_detection(j*Width+i) == True:
                canvas[j*20:(j+1)*20,i*20:(i+1)*20] = tiles[wave_[j*Width+i][0]-1].copy()

    # display the image
    cv2.imshow(window_name_,canvas)
    cv2.waitKey(1)

    if to_file_:
        cv2.imwrite("img"+str(img_id)+".png",canvas)

def render2(wave):
    for j in range(Height):
        for i in range(Width):
            sum_ = len(wave[j*Width+i])
            mean = sum_
            mean_str = str(round(mean,2))
            if len(wave[j*Width+i]) == len(oriented_candidates):
                print(Style.RESET_ALL + mean_str + "," + Fore.LIGHTBLUE_EX, end=' ')
            elif len(wave[j*Width+i]) == 1:
                print(Style.RESET_ALL + Fore.RED + mean_str + ",", end=' ')
            else:
                print(Style.RESET_ALL + Fore.GREEN + "[" + mean_str + "]"+ ",", end=' ')
        print()

    input()

# calculate fitness
def fitness(wave_):

    # calculate second order dirivative along x axis and y axis
    d1x = np.zeros((Height,Width), np.float32)
    d1y = np.zeros((Height,Width), np.float32)
    d2x = np.zeros((Height,Width), np.float32)
    d2y = np.zeros((Height,Width), np.float32)

    # get d1
    for j in range(Height):
        for i in range(Width):
            i_0 = i-1
            j_0 = j-1
            if i_0 >= 0:
                d1x[j,i_0] = wave_[j*Width+i][0] - wave_[j*Width+i_0][0]
            if j_0 >= 0:
                d1y[j_0,i] = wave_[j_0*Width+i][0] - wave_[j*Width+i][0]
    # get d2
    for j in range(Height):
        for i in range(Width):
            i_0 = i-1
            j_0 = j-1
            if i_0 >= 0:
                d2x[j,i_0] = d1x[j,i] - d1x[j,i_0]
            if j_0 >= 0:
                d2y[j_0,i] = d1y[j,i] - d1y[j_0,i]

    # compute sum of absolute value of d2
    smoothness = 0
    for j in range(Height):
        for i in range(Width):
            smoothness += abs(d2x[j,i]) + abs(d2y[j,i])

    dir_x = [0.0001,0.0001]
    dir_y = [0.0001,0.0001]
    for j in range(Height-1):
        for i in range(Width-1):
            if d1x[j,i] > 0:
                dir_x[0] += 1
            elif d1x[j,i] < 0:
                dir_x[1] += 1
            # else:
            #     dir_x[2] += 1
            if d1y[j,i] > 0:
                dir_y[0] += 1
            elif d1y[j,i] < 0:
                dir_y[1] += 1
            # else:
            #     dir_y[2] += 1

    # compute shannon entropy of dir_x and dir_y
    entropy_x = 0
    entropy_y = 0
    sum_x = 0.001
    sum_y = 0.001
    for i in range(len(dir_x)):
        sum_x += dir_x[i]
        sum_y += dir_y[i]
    for i in range(len(dir_x)):
        if sum_x != 0:
            entropy_x += -dir_x[i]/sum_x * math.log(dir_x[i]/sum_x)
        if sum_y != 0:
            entropy_y += -dir_y[i]/sum_y * math.log(dir_y[i]/sum_y)

    # min_max value of wave
    min_ = wave_[0][0]
    max_ = wave_[0][0]
    for j in range(Height):
        for i in range(Width):
            if wave_[j*Width+i][0] < min_:
                min_ = wave_[j*Width+i][0]
            if wave_[j*Width+i][0] > max_:
                max_ = wave_[j*Width+i][0]

    # compute balanceness of element distribution
    balance = 0.0001
    candidates_n = candidates_weight.copy()
    for i in range(len(candidates_n)):
        candidates_n[i] = 0
    for j in range(Height):
        for i in range(Width):
            candidates_n[wave_[j*Width+i][0]-1] += 1
    # compute average of candidates_n
    s_ = sum(candidates_n)
    for i in range(len(candidates_n)):
        candidates_n[i]/=s_
    avg_ = sum(candidates_n)/len(candidates_n)
    for i in range(len(candidates_n)):
        balance += abs(candidates_n[i]-avg_)

    fitness_ =  2 * (abs(entropy_x) + abs(entropy_y)) + smoothness + 10 * balance # - 5 * abs(min_-max_)

    # print("balance:",balance)

    # add a small purturbation to fitness
    fitness_ += np.random.rand() * 1

    return fitness_

# initialize
def init():
    # rotate candidates
    oriented_candidates.clear()
    oriented_candidates_weight.clear()
    wave_oriented.clear()
    oriented_weight_stack.clear()

    for i in range(len(candidates)):
        candidate_0 = (candidates[i],0)
        candidate_90 = rot_clockwise(candidate_0)
        candidate_180 = rot_clockwise(candidate_90)
        candidate_270 = rot_clockwise(candidate_180)
        oriented_candidates.append(candidate_0)
        oriented_candidates.append(candidate_90)
        oriented_candidates.append(candidate_180)
        oriented_candidates.append(candidate_270)
        oriented_candidates_weight.append(candidates_weight[i])
        oriented_candidates_weight.append(candidates_weight[i])
        oriented_candidates_weight.append(candidates_weight[i])
        oriented_candidates_weight.append(candidates_weight[i])

    for j in range(Height):
        for i in range(Width):
            oriented_weight_stack.append(oriented_candidates_weight.copy())
            wave_oriented.append(oriented_candidates.copy())

# conditioned initialization
def init_conditioned():
    # rotate candidates
    oriented_candidates.clear()
    oriented_candidates_weight.clear()
    wave_oriented.clear()
    oriented_weight_stack.clear()

# main function
def main():

    # init
    wave_old = []
    wave_initial = []
    
    # seed the random number generator
    np.random.seed(int(time.time()))
    
    weight_stack.clear()
    for j in range(Height):
        for i in range(Width):
            weight_stack.append(candidates_weight.copy())

    init()
    render2(wave_oriented)
    symmetry_generator(rules2)
    print("oriented candidates:",oriented_candidates)
    print("oriented candidates weight:",oriented_candidates_weight)
    input("press any key to continue...")

    img_id_ = 0

    f_min = 100000

    step_ = 0
    new_weight = Width * Height
    episode_ = 1500
                
    while True:
        
        step_ += 1

        # if len(wave_old) != 0:
        #     # alter the weight_stack
        #     for j in range(Height):
        #         for i in range(Width):
        #             c = wave_old[j*Width+i][0]
        #             weight_stack[j*Width+i] = candidates_weight.copy()
        #             weight_stack[j*Width+i][c-1] = new_weight

        # initialize the 2D-wave
        wave.clear()
        entropy.clear()
        for j in range(Height):
            for i in range(Width):
                wave.append(candidates.copy())
                entropy.append(1)

        update_wave_entropy()

        while not is_collapsed(wave):

            # 1. select the minimum entropy wavelet 
            collapse_element = find_minimum_entropy_position()

            # 2. collapse the minimum entropy wavelet
            collapse_at_position(collapse_element)

            # 3. propagate the wave function
            propagate()
            
            # clear_screen()
            # render()
            # # keyboard input
            # input()
        
        # f_ = fitness(wave)

        # 4. check for contradiction
        if contradiction_check(wave):
            clear_screen()

            render(True)
            if len(wave_old) != 0:
                render_wave(wave_old, "wave")
                render_wave(wave_initial, "wave_initial")

            print("-----------------------------------------------------")
            print("No contradiction!")
            
            # print("Fitness:", f_)

            # if len(wave_old) == 0:
            #     wave_old = wave.copy()
            #     wave_initial = wave.copy()

            # if f_ < f_min:
            #     wave_old = wave.copy()
            #     f_min = f_

            # if step_ == episode_ -1:
            #     img_id_ += 1
            #     # render current wave_old to file
            #     render_wave(wave_old, "wave_old", True,img_id_)

            #     wave_old = wave.copy()
            #     wave_initial = wave.copy()
            #     new_weight = 20
            # elif step_ >= episode_:
            #     wave_old = wave.copy()
            #     wave_initial = wave.copy()
            #     step_ = 0
            #     new_weight = Width * Height
            #     f_min = fitness(wave_old)
                
        else:
            print("Contradiction!")

        print("step: ", step_)
        input("press any key to continue...")
        

# main entry
if __name__ == "__main__":
    main()
